package main.leetcode.clockin.April;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 450.LFU缓存
 *
 * <p>设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。
 *
 * <p>get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。 put(key, value) -
 * 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。 在此问题中， 当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。
 *
 * <p>进阶： 你是否可以在 O(1) 时间复杂度内执行两项操作？
 *
 * <p>示例：LFUCache cache = new LFUCache( 2 capacity (缓存容量) );
 *
 * <p>cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 去除 key 2
 * cache.get(2); // 返回 -1 (未找到key 2) cache.get(3); // 返回 3 cache.put(4, 4); // 去除 key 1
 * cache.get(1); // 返回 -1 (未找到 key 1) cache.get(3); // 返回 3 cache.get(4); // 返回 4
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/lfu-cache
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day5 {
    private int capacity;
    private HashMap<Integer, Node> cache; // 缓冲池
    private HashMap<Integer, Queue<Node>> counter; // 存储每个频次对应链表
    private int min;

    public day5(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>(capacity);
        counter = new HashMap<>();
    }

    public static void main(String[] args) {
        day5 cache = new day5(1);
        //        cache.put(1, 1);
        //        cache.put(2, 2);
        //        System.out.println(cache.get(1));
        //        cache.put(3, 3); // 去除 key 2
        //        System.out.println(cache.get(2));
        //        System.out.println(cache.get(3));
        //        cache.put(4, 4); // 去除 key 1
        //        System.out.println(cache.get(1));
        //        System.out.println(cache.get(3));
        //        System.out.println(cache.get(4));
        cache.put(2, 1);
        System.out.println(cache.get(2));
        cache.put(3, 2);
        System.out.println(cache.get(2));
        System.out.println(cache.get(3));
    }

    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) return -1;
        updateFreq(node);
        return node.val;
    }

    public void put(int key, int value) {
        if (capacity == 0) return;
        Node node = cache.get(key);
        if (node != null) {
            node.val = value;
            updateFreq(node);
        } else {
            // 移除最近最少用到的节点
            if (cache.size() == capacity) {
                Queue<Node> tmp = counter.get(min);
                Node deadNode = tmp.iterator().next();
                tmp.remove(deadNode);
                cache.remove(deadNode.key);
            }
            node = new Node(key, value);
            Queue<Node> queue = counter.computeIfAbsent(1, k -> new LinkedList<>());
            min = 1;
            queue.add(node);
            cache.put(key, node);
        }
    }

    // 更新频次
    // 1.取出当前节点的频次对应的队列
    // 2.从该队列中移除当前节点
    // 3.如果该频次只有这一个节点（即只有这一个节点被访问了这么多次），并且该频次为最小频次，更新最小频次
    // 4.取出当前频次+1对应的队列，如果为空就新建一个并且加入counter
    // 5.把当前节点加入这个新的频次队列
    private void updateFreq(Node node) {
        int currCount = node.counter;
        // 取出当前频次对应的队列
        Queue<Node> queue = counter.get(currCount);
        queue.remove(node);
        if (currCount == min && queue.isEmpty()) min = currCount + 1;
        ++node.counter;
        // 取出新频次对应的队列
        Queue<Node> newQueue = counter.computeIfAbsent(currCount + 1, k -> new LinkedList<>());
        newQueue.add(node);
    }

    static class Node {
        int key;
        int val;
        int counter = 1;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
}
/**
 * Your LFUCache object will be instantiated and called as such: LFUCache obj = new
 * LFUCache(capacity); int param_1 = obj.get(key); obj.put(key,value);
 */
